1. Field of the Invention
This invention relates to the placement of database information on a storage device and more particularly relates to reorganizing a set of database partitions.
2. Description of the Related Art
Databases are a critical part of many computer systems due to their ability to store pieces of information, conventionally referred to as fields, along with a structure that describes links or relationships between the fields. Databases are physically stored on one or more storage devices such as disk drives, tape drives, optical drives, solid-state memory, and the like. Each field occupies a predetermined amount of storage on a storage device. The space occupied by the field is typically measured in bits or bytes. Quickly retrieving database data from a storage device is critical to most computer systems.
The time required to quickly retrieve a database data from a storage device depends, in part, on the manner that fields are physically stored on a storage device. For example, a database that is stored on a single storage device so that the fields of the database are stored adjacent to each other takes less time to retrieve than a database stored so that the fields of the database are located in several different, non-contiguous locations on the storage device. Non-contiguous fields take longer to retrieve because several different locations on the storage device are physically accessed.
When reading database data from a disk drive, for example, the read head of the disk drive is physically positioned above the area on the disk where the fields of the database are stored. If the fields are stored adjacent to each other in a contiguous area, the read head is positioned once.
In contrast, to read database data made up of non-contiguously stored fields, the read head will be physically repositioned for each non-contiguous area where fields are stored. Repositioning the read head takes longer than reading a field from the disk once the read head is positioned. Consequently, the total amount of time required to read database data stored non-contiguously is longer than the time required to read the same database data stored contiguously.
Conventional storage devices are divided into small storage areas referred to as blocks. Typically, each block has a predetermined size measured in bytes. Conventional databases set aside a portion of a storage device referred to as a partition for database data. The partition is made up of a predetermined number of blocks. The fields are stored within the blocks making up the partition. The size of the blocks and the number of blocks in a partition are typically configurable and can be optimally selected based on the characteristics of a particular database or database record or table.
The initial layout of a database on a storage device can change over time. For example, the database may have added fields, each field holding information about a particular customer. The added fields may change the partition and/or block layout on the storage device.
In addition, fields may be of variable size. Consequently, as data in fields grows or shrinks, the data may no longer fit in the original partition and block layout. If the partitions/blocks storing existing fields on the storage device do not have enough space to accommodate the longer data values, the new data will not be stored contiguously with the original fields because the storage space adjacent to the old field may be occupied. The new data will have to be stored in some other non-contiguous portion of the storage device. Consequently, the partition becomes fragmented since the field data values are no longer contiguously stored on the storage device.
Some database partitions are designed to accommodate subsequently added data in dependent overflow blocks. Dependent overflow blocks provide storage space that can be used by the database structure occupying a particular partition. If the database structure occupying the partition does not require the space provided by the dependent overflow blocks, the dependent overflow blocks go unused. A database structure is allowed to use the dependent overflow blocks that are part of its corresponding partition and is not allowed to use dependent overflow blocks that are part of another partition.
Another method to accommodate subsequently added data is to provide independent overflow blocks. Independent overflow blocks are associated with a set of partitions and can be assigned to any one of the partitions within the set. Once assigned to a particular partition, an independent overflow block is used for that particular partition and is not available to the other partitions of the set.
Independent overflow blocks are typically stored on the storage device immediately adjacent to the set of partitions. While they are not contiguous with all of the partitions of the set, the independent overflow blocks are physically close to all of the partitions of the set. As a result, the time required to retrieve data from an independent overflow block is less than would be required to retrieve data from a randomly located block on the storage device.
If increased data size cannot be accommodated by the use of both dependent and independent overflow blocks, additional blocks elsewhere on the storage device can be allocated to the partition. These additional blocks might not be located in a predictable location with respect to the rest of the partition, and thus will require additional time to retrieve.
Many different conventional databases are available, each of which may use different terms to describe the storage scheme described above. For example, in the case of a Data Entry Database (DEDB), a partition is known as an area and a block is known as a Control Interval (CI). In each area of a DEDB, a Unit of Work (UOW) is yet another example of a partition that has both dependent and independent overflow blocks. In other databases, a partition is known as a set of extents and blocks are known as pages or records.
Deleting fields or data from records in a database table or structure can also lead to unnecessarily slow table retrieval. For example, a database structure, as originally designed, may fit within a standard partition. One or more new fields can then be added to the database structure. If there is not room in the partition for the new fields, overflow blocks will be required to accommodate the new fields.
Next, one or more of the original fields stored in the partition may be deleted from the database structure. The resulting partition now has free space resulting from the deleted fields. The new fields, stored in the overflow blocks, could be stored in the free space. However, unless the new fields are moved from the overflow blocks into the free space of the partition, the new fields will continue to be stored non-contiguously in overflow blocks and the partition will remain fragmented.
As the database changes, fields and data records will be added to or deleted from database structures with the result that a greater number of the partitions of the database become fragmented. Consequently, the performance of the database degrades since it takes longer to retrieve fragmented database records from a storage device than it does to retrieve non-fragmented database records.
To resolve this performance problem, it is possible to reorganize the fragmented database partitions by rearranging the fields stored on the storage device so that the fields of a database structure are stored contiguously. Reorganization can be accomplished by recovering free space, by creating larger partitions, or by other techniques well known to those of skill in the art.
Reorganizing partitions can be very invasive because it can delay or prevent access to the records of the database. Since reorganizing partitions entails rearranging data within a storage device, fulfilling a request to access data on the storage device is delayed because the storage device will be busy processing reorganization requests. In addition, while a particular partition is being reorganized, the data records stored by that particular partition are not available to database users. Delaying or preventing access to the database is unacceptable in many database applications.
Consequently, reorganization is least invasive when performed during times of low database usage. For example, performing reorganization of a customer database at night when user demand for access to the customer database is low is less invasive than performing reorganization during business hours.
FIG. 1A illustrates a conventional method 100 for reorganizing a set of database partitions. The method begins 102 when a database administrator selects 104 a fragmentation threshold. The fragmentation threshold, as used herein, refers to a maximum level of fragmentation acceptable for partitions. The administrator selects the threshold without knowledge of the degree of partition fragmentation that exists in the database. Next, the degree to which each partition of the database is fragmented is evaluated 106 to determine a fragmentation value 154. (See FIG. 1B)
The fragmentation value 154 can be determined using a number of different methods. For example, the fragmentation value 154 can be the number of dependent or independent overflow blocks assigned to the partition. The fragmentation value 154 can also be a percentage of the partition that is not contiguous. The fragmentation value 154 can also be the amount of free space within a partition that is using overflow blocks.
Next, the partitions with a fragmentation value 154 satisfying the fragmentation threshold are reorganized 108. Once reorganization is complete, the database administrator reviews 110 the reorganization results. Reviewing the reorganization results can entail reviewing a list of the partitions that were reorganized, reviewing how much free space was recovered, and reviewing the resulting database performance improvement. The method 100 ends 112.
The method 100 described above is problematic for databases that require rapid response because the database administrator does not know the degree of partition fragmentation existing in the database before selecting the fragmentation threshold. Consequently, the database administrator is unable to control the number of partitions that will be reorganized. If the database administrator selects a threshold that is too low, a large number of partitions will be reorganized. The time required to reorganize this large number of partitions may not fit within the period of low usage.
For example, a customer database may have low usage for six hours each night during which a database administrator can perform partition reorganization with minimal impact to database users. If the database administrator selects a threshold that leads to a large number of partitions being reorganized, the partition reorganization may not finish within the six hour low usage period. Instead, the partition reorganization may extend into a high usage period where the impact of partition reorganization on users is intolerable.
Alternatively, if the database administrator selects a fragmentation threshold that is too high, a small number of partitions will be reorganized. This can also be problematic since a database administrator may want to maximize the number of partition reorganizations that occur during the six hour low usage period. If too few partitions are reorganized, the low usage period will not be used effectively, especially if the database administrator is not present to initiate another partition reorganization once the original partition reorganization is complete.
At the time the database administrator makes a fragmentation threshold selection, he does not know whether the fragmentation threshold he selects will be too low, too high, or just right because he does not know the degree of partition fragmentation existing in the database. Consequently, the database administrator uses a trial and error process of selecting a fragmentation threshold that can impose undesirable delays on database users.
FIG. 1B is a chart 150 illustrating an example set of database partition identifiers 152 and corresponding fragmentation values 154. The fragmentation value 154, in this example, is a percentage representing the amount of data in the partition that is fragmented. Suppose, the fragmentation threshold is three percent. The shaded rows 156 of the chart 150 represent partitions that have a fragmentation value 154 greater than or equal to the fragmentation threshold of three percent. In this example, the three percent fragmentation threshold results in more than half of the database being reorganized which may take an unacceptable amount of time.
Had the database administrator been aware that more than half of the partitions would be reorganized as a result of this threshold choice of three percent, he may have increased his threshold choice to reduce the number of partitions that would be reorganized. However, the database administrator is unable to do this because he is not able to see the fragmentation values 154 before selecting a fragmentation threshold.
From the foregoing discussion, it should be apparent that a need exists for a method for more efficiently reorganizing a set of database partitions. The method should ensure that a database administrator has greater control over the number of database partitions to be reorganized. Additionally, the method should provide a method to estimate both the amount of resources that will be required for a particular reorganization and the expected performance improvement that will result from the reorganization.